Property graphs are emerging as the standard for graph databases. A property graph is a data structure in which data is represented as vertices (i.e., nodes) and edges connecting the vertices. The edges are directional in that they have a source at one vertex and a terminus at another vertex (i.e., each edge has a head and a tail). Both the vertices and the edges can be associated with data representing their properties.
Property graphs are multi-relational in that they include many types of edges that represent different types of relationships between the vertices. More specifically, each of the vertices in a property graph can have a unique identifier, a label, one or more outgoing edges, one or more incoming edges, and one or more properties. Additionally, each of the edges can have a unique identifier, a tail connecting to a first vertex, a head connecting to a second vertex, a label that denotes the type of relationship between its two vertices, and a collection of properties. For example, a first vertex of a property graph labeled “Sam” may be directed to a second vertex labeled “Dave” by an edge labeled “knows.” The second vertex (i.e., “Dave) can be directed to a third vertex labeled “Susan” by an edge labeled “teaches.” The vertices may have one or more associated properties, such as age, identification number, location, and college. The edge may also have one or more associated properties, such as source and time.
A property graph comprised of many such vertices and edges can be used to determine associations between remote vertices. For example, using a semantic search process, a database query may determine anyone associated with Sam who attends College X (i.e., a name of a particular college or university) defined in the properties by iteratively traversing the property graph from a first vertex (e.g., Sam) to a destination vertex associated with the target of the query (e.g. attend College X).
Content addressable memory (CAM) devices are a special type of memory that search databases at high-speeds by searching multiple records in parallel. A CAM typically includes an array of storage cells arranged in rows and columns, where each row of the CAM array corresponds to a stored word of reference data. The storage cells in a given row couple to a word line and a match line associated with the row. The word line is used to select the row for a read/write operation, while the match line is used to signal a hit (i.e., a match) or a miss during the search operation. Each column of the CAM array corresponds to the same bit position in all of the words. The storage cells in a particular column are coupled to a pair of bit lines and a pair of search-lines associated with the column. During a search operation, the match line develops a logic state that indicates whether the word stored in the row matches a word of search data. The search data is applied to each pair of search lines, which have a pair of complementary binary signals or unique ternary signals thereon that represent a bit of the search data. Each CAM cell changes the voltage on the associated match line if the storage cell stores a bit that does not match the bit represented on the attached search lines. If the voltage on a match line remains unchanged during a search, the word stored in that row of storage cells matches the entire word of search data indicating a hit between the word of reference data and the search data.